package com.leetcode.solution.s8x;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Combine88 {
    public static void main(String[] args) {
        List<List<Integer>> combineList = new Combine88().combine(4, 2);

        for (List<Integer> integers : combineList) {
            for (Integer integer : integers) {
                System.out.print(integer + ", ");
            }
            System.out.println("");
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> tmpCombineList = subCombine(n, 1, k);
        List<List<Integer>> combineList = new ArrayList<>();
        for (List<Integer> tmpCombine : tmpCombineList) {
            if (tmpCombine.size() == k) {
                combineList.add(tmpCombine);
            }
        }

        return combineList;
    }

    private List<List<Integer>> subCombine(Integer n, Integer now, Integer k) {
        List<List<Integer>> combineList = new ArrayList<>();
        List<Integer> tmpList;
        if ( now.equals(n) ) { // 最后一个元素
            tmpList = new ArrayList<>();
            tmpList.add(now);
            combineList.add(tmpList);

            tmpList = new ArrayList<>();
            combineList.add(tmpList);

            return combineList;
        }

        // 递归查找后续组合
        List<List<Integer>> subCombineList = subCombine(n, now+1, k);
        for (List<Integer> subCombine : subCombineList) {
            if (subCombine.size() <= k) { // 元素数足够
                combineList.add(subCombine);

                if (subCombine.size() < k) {
                    tmpList = subCombine.stream().collect(Collectors.toList());
                    tmpList.add(now);

                    combineList.add(tmpList);
                }
            }
        }

        return combineList;
    }
}
